#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005];
int w[1000006<<2];
int lz[1000006<<2];
void pushup(int now){
    w[now]=max(w[now<<1],w[now<<1|1]);
}
void pushdown(int now){
    if(lz[now]){
        w[now<<1]+=lz[now];
        w[now<<1|1]+=lz[now];
        lz[now<<1]+=lz[now];
        lz[now<<1|1]+=lz[now];
    }
    lz[now]=0;
}
void build(int now,int l,int r){
    if(l+1==r){
        w[now]=-1e15;
        return ;
    }
    lz[now]=0;
    int mid=(l+r)>>1;
    build(now<<1,l,mid);
    build(now<<1|1,mid,r);
    pushup(now);
}

void fz(int now,int l,int r,int c,int p){
    if(l+1!=r)pushdown(now);
    if(l+1==r){
        w[now]=p;
        return ;
    }
    int mid=(l+r)>>1;
    if(c<mid)fz(now<<1,l,mid,c,p);
    else fz(now<<1|1,mid,r,c,p);
    pushup(now);
}
void ad(int now,int l,int r,int L,int R,int c){
    if(l+1!=r)pushdown(now);
    if(R<=l||r<=L)return;
    if(L<=l&&r<=R){
        w[now]+=c;
        lz[now]+=c;
        return;
    }
    int mid=(l+r)>>1;
    ad(now<<1,l,mid,L,R,c);
    ad(now<<1|1,mid,r,L,R,c);
    pushup(now);
}
int ge(int now,int l,int r,int p){
    if(l+1!=r)pushdown(now);
    if(l+1==r)return w[now];
    int mid=(l+r)>>1;
    if(p<mid)return ge(now<<1,l,mid,p);
    else return ge(now<<1|1,mid,r,p);
}
signed main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;

        for(int i=1;i<=n;i++)cin>>a[i];
        a[n+1]=0;
        const int ma=*max_element(a+1,a+1+n)+1;
        build(1,0,ma+1);
        fz(1,0,ma+1,0,0);
        for(int i=1;i<=n+1;i++){
            if(a[i]==a[i-1]){
                
                int c=ge(1,0,ma+1,a[i])+a[i];
                c=max(c,w[1]);
                int q=ge(1,0,ma+1,a[i-1]);
                q=max(q,c);
                fz(1,0,ma+1,a[i-1],q);
                ad(1,0,ma+1,0,a[i],a[i]);
                ad(1,0,ma+1,a[i]+1,ma,a[i]);
            }else{
                int c=ge(1,0,ma+1,a[i])+a[i];
                c=max(c,w[1]);
                int q=ge(1,0,ma+1,a[i-1]);
                q=max(q,c);
                fz(1,0,ma+1,a[i-1],q);

            }
        }
        cout<<w[1]<<'\n';
    }
    return 0;
}